package tree.threadedBinaryTree;

import lombok.NoArgsConstructor;

/**
 * 中序化二叉树 && 线索二叉树的遍历
 */
public class ThreadBinaryTree {
    public static void main(String[] args) {
        ThreadBinaryTree threadBinaryTree = new ThreadBinaryTree();
        HeroNode s1 = new HeroNode(1, "1");
        HeroNode s3 = new HeroNode(3, "3");
        HeroNode s6 = new HeroNode(6, "6");
        HeroNode s8 = new HeroNode(8, "8");
        HeroNode s10 = new HeroNode(10, "10");
        HeroNode s14 = new HeroNode(14, "14");
        threadBinaryTree.setRoot(s1);
        s1.setLeft(s3);
        s1.setRight(s6);
        s3.setLeft(s8);
        s3.setRight(s10);
        s6.setLeft(s14);
        threadBinaryTree.infixOrder(); // 中序遍历顺序为:8 3 10 1 14 6
        threadBinaryTree.threadedNodes();
        // 测试10号节点
        HeroNode left = s10.getLeft();
        HeroNode right = s10.getRight();
        System.out.println("10号前驱节点为" + left + ". 后继为" + right);
        threadBinaryTree.threadInfixOrder();
//        threadBinaryTree.threadInfixOrderV2();
//        threadBinaryTree.preOrder();
//        threadBinaryTree.preThreadNodes(root);
//        System.out.println("==");
//        threadBinaryTree.preSearchOrder();


    }

    private static HeroNode root;
    private static HeroNode pre; // 在递归线索化时，pre保留前一个节点。

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    public static HeroNode getRoot() {
        return root;
    }

    /**
     * 线索化的关键代码 中序化二叉树
     */
    public static void threadedNodes(HeroNode node) {
        if (node == null) {
            return;
        }
        //(1 先线索化左子树，增加判断条件避免死循环
        if (node.getLeftType() != 1) {
            preThreadNodes(node.getLeft());
        }
        //(2 线索化当前子树
        // 此时判断左节点是否为空，并设置前驱，第一次pre = null
        if (node.getLeft() == null) {
            // 一开始定位到最左节点, pre 为null
            node.setLeft(pre);
            node.setLeftType(1);
        }
        // 只有pre才能指向后继
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;
        //(3 线索化右子树

        if (node.getRightType() != 1) {
            preThreadNodes(node.getRight());
        }
    }

    public static void threadedNodes() {
        threadedNodes(getRoot());
    }

    /**
     * 线索化前序二叉树
     */
    public static void preThreadNodes(HeroNode node) {
        if (node == null) {
            return;
        }
        // 先线索化自身节点
        // 此时判断左节点是否为空，并设置前驱，第一次pre = null
        if (node.getLeft() == null && node.getLeftType() != 1) {
            // 一开始定位到最左节点, pre 为null
            node.setLeft(pre);
            node.setLeftType(1);
        }
        // 只有pre才能指向后继
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;
        if (node.getLeftType() != 1) {
            preThreadNodes(node.getLeft());
        }
        if (node.getRightType() != 1) {
            preThreadNodes(node.getRight());
        }
    }

    /**
     * 前序线索遍历
     */
    public void preSearchOrder(){
        root.threadPreOrder();
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        if (root != null) {
            this.root.infixOrder();
        } else System.out.println("二叉树为空，无法遍历");
    }

    public void preOrder() {
        if (root != null) {
            this.root.preOrder();
        } else System.out.println("二叉树为空，无法遍历");
    }

    /**
     * 对中序线索二叉树的遍历
     */
    public void threadInfixOrder() {
        getRoot().threadInfixOrder();
    }

    public void threadInfixOrderV2() {
        getRoot().threadInfixOrderV2();
    }

    @lombok.Data
    @NoArgsConstructor
    public static
            /**
             * 这只是创建一个节点
             */
    class HeroNode {
        private int id;
        private String name;
        private HeroNode left;
        private HeroNode right;
        private int leftType;   // 左节点的类型， 1：指向前驱 0 ：指向子树
        private int rightType; // 同上

        public HeroNode(int id, String name) {
            this.id = id;
            this.name = name;
        }

        @Override
        public String toString() {
            return "HeroNode{" +
                    "id=" + id +
                    ", name='" + name + '\'' +
                    '}';
        }


        /**
         * 中序遍历
         */
        public void infixOrder() {
            if (this.left != null) {
                this.left.infixOrder();
            }
            System.out.println(this);
            if (this.right != null) {
                this.right.infixOrder();
            }

        }

        /**
         * 线索化的中序遍历 方法1：使用递归找type为0的
         */
        public void threadInfixOrder() {
            if (this.left != null && this.getLeftType() != 1) {
                this.left.threadInfixOrder();
            }
            System.out.println(this);
            if (this.right != null && this.getRightType() != 1) {
                this.right.threadInfixOrder();
            }
        }

        /**
         * 线索化的中序遍历  方法2：不使用递归 这个才是最优解答
         * 思路：从左子树找到最左节点，找type==1的后继，如果type=0，手动后移
         * 后来到右子树了，同样也要找到最左节点，再后继...
         */
        public void threadInfixOrderV2() {
            HeroNode node = root;
            while (node != null) {
                /**
                 * 这段代码会运行二次，第一次找到左子树的最左节点
                 *                  第二次找到右子树的最左节点
                 */
                while (node.getLeftType() == 0) {
                    node = node.getLeft();
                }
                // 打印当前节点
                System.out.println(node);
                // 找到后继
                while (node.getRightType() == 1) {
                    node = node.getRight();
                    System.out.println(node);
                }
                // 当type！=1时，让他继续往下走
                node = node.right;
            }
        }

        public void preOrder() {
            System.out.println(this);
            if (this.left != null) {
                this.left.preOrder();
            }
            if (this.right != null) {
                this.right.preOrder();
            }
        }


        public static void threadPreOrder() {
            HeroNode node = root;
            while (node != null) {
                /**
                 * 这段代码会运行二次，第一次找到左子树的最左节点
                 *                  第二次找到右子树的最左节点
                 */
                while (node.getLeftType() == 0) {
                    // 打印当前节点
                    System.out.println(node);
                    node = node.getLeft();
                }
                System.out.println(node);
                // 找到后继
                while (node.getRightType() == 1) {
                    node = node.getRight();
                    System.out.println(node);
                }
                // 当type！=1时，让他继续往下走
                if (node.getRightType() != 1) {
                    node = node.right;
                }
            }
        }
    }
}



